package cn.edu.besti.cs1623.M20162319;

/**
 * Created by hasee on 2017/10/16.
 */
public class Sorting {
    public static void  selectionSort(Comparable[]data){
        int min;

        for (int index = 0; index < data.length-1;index++){
            min = index;
            for (int scan = index+1;scan<data.length;scan++)
                if (data[scan].compareTo(data[min])<0)
                    min = scan;

            swap(data,min,index);
        }
    }
    private static void swap(Comparable[] data,int index1,int index2){
        Comparable temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
    public static void insertionSort (Comparable[]data){
        for (int index = 1;index < data.length;index++)
        {Comparable key = data[index];
        int position = index;
        while (position > 0 && data[position-1].compareTo(key)>0){
            data[position] = data[position-1];
            position--;
        }
        data[position] = key;}
    }
    public static void bubblesort(Comparable[]data){
        int position,scan;
        for (position = data.length - 1;position>=0;position--){
            for (scan = 0;scan<=position-1;scan++)
                if (data[scan].compareTo(data[scan+1])>0)
                    swap(data,scan,scan+1);
        }
    }
    public static void quickSort(Comparable[]data,int min, int max){
        int pivot;

        if (min<max){
            pivot = partition(data,min,max);
            quickSort(data, min, pivot-1);
            quickSort(data,pivot+1,max);
        }
    }
    private static int partition(Comparable[]data,int min,int max){
        Comparable partitionValue = data[min];

        int left = min;
        int right = max;

        while (data[right].compareTo(partitionValue)>0)
            right--;
        if (left<right)
            swap(data,min,right);
        return right;
    }
    public static void mergeSort(Comparable[]data,int min,int max)
    {if (min<max)
    {
        int mid = (min+max)/2;
        mergeSort(data, min, mid);
        mergeSort(data,mid+1,max);
        merge(data,min,mid,max);
    }}
    public static void merge(Comparable[]data,int first,int mid,int last){
        Comparable[]temp = new Comparable[data.length];

        int first1 = first,last1 = mid;
        int first2 = mid+1,last2 = last;
        int index = first1;

        while (first1 <= last1 && first2<=last2)
        {if (data[first1].compareTo(data[first2])<0){
            temp[index] = data[first1];
            first1++;
        }index++;}
        while (first1<=last1)
        {temp[index] = data[first1];
        first1++;
        index++;}
        while (first2<=last2){
            temp[index] = data[first2];
            first2++;
            index++;
        }
        for (index = first;index<=last;index++)
            data[index] = temp[index];
    }
}
